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
[email protected]

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