Árangursrík Forritun og Lausn Verkefna
This course provides and introduction to a wide variety of algorithms and problem solving methods, with an emphasis on programming and how to make use of them.
Instructor: Atli Fannar Franklín and Arnar Bjarni Arnarson
Term: Fall
Course Overview
This introductory course on machine learning covers fundamental concepts and algorithms in the field. By the end of this course, students will be able to:
- Learn fundamental problem solving methods, and how to apply them.
- Learn a wide variety of algorithms, and how they function.
- Gain experience with hands-on programming and problem solving.
Prerequisites
- Fundamentals of programming.
- Fundamentals of time complexities and algorithms.
Textbooks
- Primary: Slides on github
- Reference: “Competitive Programming” by Steven Halim
- Reference: “Competitive Programmer’s Handbook” by Antti Laaksonen
Grading
- Assignments: 60%
- Midterm Exam: 20%
- Final Exam: 20%
- Bonus Problem Sets: 10%
Schedule
| Week | Topic |
|---|---|
| 1 | Using Kattis, Time Complexity, Languages and Standard Libraries. |
| 2 | Straingforward Implementations, Ad-hoc and Complete Search. |
| 3 | Greedy Algorithms and Binary/Ternary search. |
| 4 | Divide & Conquer and Dynamic Programming Part 1. |
| 5 | Dynamic Programming Part 2. |
| 6 | Data Structures, Heap, Union Find, Sliding Window, Range Quereis (Prefix Sum, Square Root Decomposition, [Lazy Propagation] Segment Trees), Sparse Table. Midterm Exam. |
| 7 | Math Basics and Number Theory, Primality, Factoring, Divisors and more. |
| 8 | Unweighted/Undirected Graphs, Breadth/Depth First Search. |
| 9 | Weighted and/or Directed Graphs, Dijkstra, Kruskal, Bellman-Ford, Topsort, Floyd-Warshall. |
| 10 | Maximum Flow. |
| 11 | Combinatorics, Counting, Probability and Game Theory. |
| 12 | String processing, KMP, Tries and Hashing. |