Introduction to computer science II 1000-112bWI2a

1. Elements of complexity analysis: the size of a problem. Time complexity and space complexity. Practical computation of algorithm complexity (sorting, binary search). The complexity of recursive algorithms. (3 lectures)
2. Pointers and abstract data structures (lists, queues, stacks, priority queues, binary search trees). (4 lectures)
3. Graphs: representations and elementary graphs algorithms (breadth-first search, deph-first search). (6 lectures)
4. NP-complete and undecidable problems. 2 lectures)

Type of course

obligatory courses

Prerequisites (description)

(in Polish) Oczekuje się dobrej znajomości zagadnień ujętych w sylabusie przedmiotu Wstęp do informatyki I.

Bibliography

1. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, The MIT Press, Cambridge, Massachusetts, 1989.

Additional information

Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:

Bachelor's degree, first cycle programme, Mathematics

Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system:

Description of 1000-112bWI2a in USOSweb