NETB291 Competitive Programming, Part 2

Annotation:

The course is more theoretical. It is an extension of the NETB290 Competitive Programming - Part 1 course but is independent of it. The course aims to prepare students to solve tasks, requiring the creation of more complex algorithms. During the course we will study the entire path from problem creation to solutions analysis - data analysis, review of existing algorithms to solve specific problems, selection of a suitable algorithm, modification of an existing or design of a new algorithm, selection of data structures, programming, testing of the program, algorithm and program performance analysis. The programming language is C/C++.

прочети още
Networking Technologies

Lecturers:

Assoc. Prof. Nikolay Kirov, PhD
Assoc. Prof. Metodi Traykov, PhD

Course Description:

Competencies:

Students who have successfully completed the course:

1) know:

• Analysis of the effectiveness of an algorithm;

• Algorithm design;

• Data analysis;

• Analysis and modifications of existing algorithms for sorting and searching;

• STL in C++;

2) can:

• To design and implement complex algorithms for solving applied and scientific problems;

• Modify existing or build new algorithms;

• To analyze the effectiveness of an algorithm and a program.
Prerequisites:
Students to have knowledge and/or skills:

- Basic operators in the programming language C and/or C++;

- Knowledge and programming skills in C and/or C++.

- Functional programming in C++;

- Working with a text editor;

- Access to resources on the Internet;

- General computer literacy.

Will be good if the students have completed the NETB290 Competitive Programming - Part 1 course but it is not required.

Types:
Full-time Programmes

Types of Courses:
Lecture

Language of teaching:
Bulgarian

Topics:

  1. Technology for Competitive Programming and Algorithm Evaluation.
  2. Dynamic Programming
  3. Graph representation. Traversal of graphs.
  4. Programming Contest 1
  5. Programming Contest 1
  6. Minimum Spanning Tree and Shortest Paths. Graph - Common tasks.
  7. Greedy algorithms
  8. Geometric tasks.
  9. Programming Contest 2
  10. Programming Contest 2
  11. Mathematical tasks
  12. Coding and copresing
  13. Warshall's algorithm and topological sorting
  14. Programming Contest 3
  15. Programming Contest 3

Bibliography:

Books:

1. Antti Laaksonen, Competitive Programmer's Handbook, 2017, https://cses.fi/book.html

2. Cormen T., Lеiserson C., Rivest R., Introduction to Аlgorithms, MIT Press/McGraw-Hill, Cambridge, MA, 1990.

3. Wirth N., Algorithms + data structures = programs. Prentice-Hall, Englewood Cliffs, N. J. 1973.

4. Simon Harris, James Ross, Beginning Algorithms, Indianapolis, IN: Wiley, 2006

5. MIT 6.006 Introduction to Algorithms, Fall 2011 (https://www.youtube.com/playlist?list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb)

6. Data Structure Visualizations (https://www.cs.usfca.edu/%7Egalles/visualization/Algorithms.html)

Additional materials

1. Leen Ammeraal, Algorithms and Data Structures in C++, 1 eds, John Wiley & Sons, 1996

2. Robert Sedgewick, Algorithms in C. Volume 1 and 2, Addison-Wesley Professional, 2002

4. Красимир Манев, Алгоритми в графи. Основни алгоритми, КЛМН, 2013.

5. MIT 6.006 Introduction to Algorithms, Fall 2011

Assessment:

The practical exam is conducted according to the rules of the final exam competition: the students have tasks and a computer on which to write the solutions to the tasks - working C++ programs.