CSC 2304
DATA STRUCTURES & ALGORITHMS
Dr. Mykhailo Medvediev School of Information Technologies and
Ph.D., Assistant Professor Engineering (SITE),
Teaching hours: ADA University, Baku, Azerbaijan
Mon 13:00 – 14:15 Spring 2023
Office Hours: TBD Office phone number: 413
ECTS – 6
mmedvediev@ada.edu.az
Introduction and Basic Concepts
The concept of algorithm is fundamental to computer science. Algorithms exist for many
common problems and designing efficient algorithms plays a crucial role in developing large-scale
computer systems. The course particularly focuses on underlying principles of analysis of algorithms.
The students get knowledge about complexity of algorithms and learn their applications in such
topics as graphs, sort and search, combinatorics. They will learn such algorithmic techniques like
recursion with memorization, dynamic programming, greedy. The course equips students with
necessary knowledge and skills to understand the basic data structures and general techniques for the
analysis and coding these algorithms using C/C++ or Java language.
This course is a part of the Bachelor program in Computer Sciences of ADA University and
considered mandatory for the second year graduate students. Due to the specific nature of the subject,
the course Data structures & Algorithms tightly connected with Programming principles.
The prerequisite for this course is Programming Principles I (or II). The students must have
knowledge in C or Java programming language.
Students must bring their laptops during classes.
Aims and Learning Outcomes
The academic aim of the course is to expand and deepen the students’ knowledge in data
structures and analysis of algorithms and learn them to code effectively.
Upon successful completion of this course, students will be able to:
1. Demonstrate critical thinking, analytical reasoning, and problem solving skills.
2. Apply appropriate algorithms and algorithm techniques to solve problems.
3. Identify a problem and analyze it in terms of its significant parts and the information
needed to solve it.
4. See the differences between effective and non-effective algorithms.
5. Implement complicated problems involving combinations of algorithms on their own.
Workload
It is estimated that the students will need to solve up to 10 programming problems per week.
Students will need from 4 to 6 hours per week for assignments.
Additional materials, articles and book chapters will be provided by instructor.
Assessment
The bulk of the assessment is weekly programming tasks at www.e-olymp.com online judge
systems, which involve solving problems using efficient algorithms learned in lectures. Students spend
up to 6 hours per week on these assignments and often consult frequently with section instructors for
help. Exercises for assessment are available at e-olymp.com in a separate group only for students and
their tutor. Deadline for each contest is 2 weeks. A mid-term exam and a final exam account for a
significant portion of the grade.
The overall assessment of students will be divided as follows:
4 Homeworks = 4 * 8% = 32%
5 Quizzes = 5 * 6% = 30%
Midterm exam: 15%
Final exam: 23%
Attendance and tardiness
Attendance is an indispensable element of the educational process. In compliance with
Azerbaijani legislation, instructors are required to monitor attendance and inform the Registrar and the
Dean of the student’s respective School when students miss significant amounts of class time.
Azerbaijani legislation mandates that students who fail to attend at least 75% of classes will fail the
course.
Structure of the Course
Week Topics Learning Outcomes (students will be able to)
1 Complexity of Ttime and memory complexity
algorithms. Understand the principles of recursion
Asymptotic notations xn, GCD, LCM, Cnk, Fibonacci
2 Principles of recursion Exponentiation
Memorization GCD, LCM applications
Fibonacci sequence, memorization
Prime numbers. Sieve of Eratosthenes
3 Recursive programs Applications of recursive algorithms
Problems solving
4 Dynamic Programming Linear dynamic programming
2-dim dynamic programming
Turtle problems
Quiz 1
HOMEWORK 1
5 Stack data structure Stack & Deque implementation
Deque data structure Majority element
Problems with Stack & Deque
6 Linked List Linked List implementation
7 Binary tree Trees implementation
HOMEWORK 2
Quiz 2
8 Sorting algorithms STL sort, swap sort
How to write a comparator
Count inversions
Counting sort
Quiz 3
MIDTERM
9 Graphs and their Adjacency Matrix
representations Adjacency List
List of edges
Graph representation problems
10 Graphs: Depth First Implement depth first search
Search Connectivity problems
11 Depth First Search Cycles detection for directed & undirected graphs
applications DFS applications
HOMEWORK 3
Quiz 4
12 Grids & Labyrints Grids & Labyrints problems
13 Graphs: Breadth first BFS Implementation
search BFS applications
14 Dijkstra algorithm Dijkstra algorithm implementation
Problems solving
HOMEWORK 4
Quiz 5
E-olymp Problems to solve:
www.e-olymp.com
Week 1: January 23 - 29
Recursive functions: factorial, power, fibonacci numbers.
2. Digits (number of digits)
1603. The sum of digits
1658. Factorial (n!)
2999. Function-10 (recursive function)
8609. Recursion – 1
Exponentiation:
273. Modular Exponentiation
4439. Exponentiation
Fibonacci:
3258. Fibonacci Sequence
4730. Fibonacci
Binomial coefficient:
3260. How Many? (Cnk)
Greater Common Divisor & Least Common Multiple:
1601. GCD two numbers
1602. LCM of two positive integers
Different problems:
5123. Hailstone HOTPO
141. The minimal sum of digits
8377. Persistent number
Math problems:
9052. Headshot
10452. The essay
10405. Teleportation
2,1603,1658,2999,8609,273,4439,3258,4730,3260,1601,1602,5123,141,8377,9052,10452,10
405
Week 2: January 30 – February 5
Exponentiation
5198. Modular exponentiation
9644. Sum of powers
9557. Bins and balls
9592. Concatenation of two palindromes
GCD, LCM
7363. GCD
136. The segment
6941. Sum of GCD
Fibonacci numbers
4730. Fibonacci
263. Three ones
4469. Domino
5091. Explosive containers
5092. Honeycomb
8295. Fibonacci string generation
Prime numbers. Sieve of Eratosthenes
1616. Prime number?
572. The lesson of mathematics
4739. Sieve of Eratosthenes
3843. Primes
5198,9644,9557,9592,7363,136,6941,4730,263,4469,5091,5092,8295,1616,572,4739,3843
Week 3: February 6 - 12
Recursive functions
1207. Sqrt log sin
1211. Infinite sequence
1212. Infinite sequence – 2
10165. Function f(n)
10296. Recursive function 1
3936. Towers of Hanoi
6155. Wrong monks
8304. Fun function
1520. Odd divisors
1517. Simple addition
1343. Bad substring
5973. Out of the line!
6583. Counting ones
2177. Function Run Fun
1207,1211,1212,10165,10296,3936,6155,8304,1520,1517,1343,5973,6583,2177
Week 4: February 13 – 19
Linear DP
1560. Decreasing number
1619. House robber
9628. Frog
799. Buying tickets
987. Nails
44. The number of ones
798. Platforms
806. Platforms 3
Square DP
683. Partial matrix sum
4018. Turtle
4019. Turtle restoring
4021. Knight move
1704. Clever turtle
3174. North East King
5101. Hodja Nasreddin
1560,1619,9628,799,987,44,798,806,683,4018,4019,4021,1704,3174,5101
Week 5: February 20 - 26
Stack
6122. Simple stack
6123. Stack with error protection
5087. Implement a stack
5327. Bracket sequence
2479. Parentheses balance
5060. Revere Polish notation
940. Majority element
4259. Minimum in the stack
1776. Rails
Deque
6128. Simple deque
6129. Deque with error protection
8355. Book shelf
3161. Deques on 6 Megabytes
10143. Throwing cards away
10142. Power of time
6122,6123,5087,5327,2479,5060,940,4259,1776,6128,6129,8355,3161,10143,10142
Week 6: February 27 – March 5
Linked List
9898. LinkedList Sum
9899. LinkedList Length
10041. Print in reverse order
10042. LinkedList Cycle
10043. LinkedList Cycle starting point
10044. LinkedList Merge
10047. LinkedList Intersection
10380. LinkedList Middle
10748. LinkedList Remove Cycle
10763. LinkedList Cycle Length
10802. LinkedList Distance to Cycle
10803. LinkedList Delete first element
9898,9899,10041,10042,10043,10044,10047,10380,10748,10763,10802,10803
Week 7: March 6 – 12
Binary trees
10063. Tree find
10061. Tree minimum element
10062. Tree maximum element
10146. Tree next
10147. Tree previous
10109. Tree minimum depth
10110. Tree maximum depth
10057. Tree PreOrder Traversal
10059. Tree InOrder Traversal
10060. Tree PostOrder Traversal
10064. Tree sum of elements
10111. Tree sum of left leaves
10112. Tree Balanced
10113. Tree sum of leaves
10114. Tree invert
10115. Tree Symmetric
10063,10061,10062,10146,10147,10109,10110,10057,10059,10060,10064,10111,10112,
10113,10114,10115
March 13 – 19
MIDTERM
March 20 – 26
NOVRUZ HOLIDAYS
Week 8: March 27 – April 2
Sorting
2321. Sort
4738. Sorting
4848. Quick sort
Invertions
8735. Train swappung
1457. “Sort” station
Sorting chars / strings
8316. Sort the letters
2166. Anagrams
2323. Numbers from digits
2325. Two numbers
8317. Square of difference
9648. Sort the digits of numbers
Counting sort
2327. Counting sort
2617. Birthdays
145. Squares
7809. Morning exercises
Comparators
972. Sorting time
1462. Tricky sorting
8236. Sort evens and odds
8637. Sort the points
3937. Digitqal root
10246. ACM Sort
2321,4738,4848,8735,1457,8316,2166,2323,2325,8317,9648,2327,2617,145,7809,972,1462,
8236,8637,3937,10246
Week 9: April 3 – 9
Adjacency matrix: count number of edges
992. Cities and roads
5072. Count number of edges
Adjacency matrix: properties
994. Coloured rain
Convert from one representation to another
2471. From adjacency matrix to the list of edges
4766. From adjacency matrix to the list of edges – 2
3981. From adjacency matrix to adjacency list
3982. From adjacency list to adjacency matrix
4763. From list of edges to adjacency matrix
Checking the graph properties
2470. Checking for an undirected graph
3987. Complete graph
4761. Loops
5073. Multiedges
5080. Number of hanging vertices 1
5088. Number of hanging vertices 2
Degree of vertices
993. Traffic lights
4764. Degrees of vertices
5074. Degrees of vertices by a list of edges
5076. Regular graph
3986. Sources and sinks
Adjacency list
2472. Operations on graph
992,5072,994,2471,4766,3981,3982,4763,2470,3987,4761,5073,5080,5088,993,4764,5074
,5076,3986,2472
Week 10: April 10 – 16
Depth first search:
8760. Depth first search
978. Get a tree
977. Is it a tree?
6033. Kastenlauf
4077. Corporation salary
Connected components:
2269. Connected components
982. Connectivity
4000. Depth search
5339. Gnomes and houses
776. Roads
Trees:
2157. Sum
10653. XOR Sum
10684. Roads improvement
8760,978,977,6033,4077,2269,982,4000,5339,776,2157,10653,10684
Week 11: April 17 – 23
Timestamps:
8761. Depth first search – timestamps
9654. Depth first search on a disconnected graph
Cycles:
1390. Car race
4004. Is there a cycle?
2270. Find a cycle
7945. Dwarves
Bicoloring:
3165. Bicoloring
4002. Cheating away!
DFS on grids (labyrinths):
2590. Space Exploration
2168. Square punch
1063. Cell removal
1685. Lands of Antarctica
4001. Area of the room
7024. Red and Black
8761,9654,1390,4004,2270,7945,3165,4002,2590,2168,1063,1685,4001,7024
Week 12: April 24 – 30
Breadth first search:
2401. Breadth first search
4852. The shortest distance
5338. Complete graph – 2
4819. Maximum by minimum
Path in bfs:
4853. The shortest path
BFS from multiple sources:
4369. Arson
10049. Bitmap
0-1 BFS:
10056. Breadth first search 0 – 1
10048. Reverse the graph
Longest path:
10050. Longest path in a tree
Advanced BFS:
9635.Transport system
10116. Almost shortest path
2401,4852,5338,4819,4853,4369,10049,10056,10048,10050,9635,10116
Week 13, 14: May 1 – 13
Dijkstra – weight matrix
2351. Dijkstra
4856. The shortest path
8348. Distance between vertices
34. The word of sponsor
1388. Petrol stations
5850. Mathematical platforms
9608. Taxi
Dijkstra – priority queue
2965. Distance between the vertices
625. Distance between the vertices
7710. Change of Scenery
10456. Server
2351,4856,8348,34,1388,5850,9608,2965,625,7710,10456
