Bilgisayar Mühendisliği Bölümü
DATA STRUCTURES AND ALGORITHMS Syllabus Administrative Information GIT – Computer Engineering Department
Catalog Description: Introduction to data structure and algorithms. Efficiency of algorithms. Abstract data structures and their implementations: – Linear Structures: list, stack, queue, hashing. – Tree structures: binary trees, AVL trees, priority queues. – Graphs and algorithms: shortest paths, minimum spanning trees.
Sorting algorithms.
GIT – Computer Engineering Department
2
Educational Objectives: This course aims to introduce you some basic data structures and algorithms which are to be used as tools in designing solutions to problems. You will become familiar with the specification, usage, implementation and analysis of these data structures and algorithms. By the end of this course you should be able to : • Design algorithms to solve real-life problems using the tools introduced, • Analyze your solution, • Efficiently implement your solution.
GIT – Computer Engineering Department
3
Books Textbook: – Elliot Koffman, Paul Wolfgang, Objects, Abstraction, Data Structures and Design Using C++, Wiley, 2005.
Other Books: – M. A. Weiss, Data Structures and Algorithm Analysis in C++, Addison Wesley, 2006. – Cormen, Leiserton, Rivest, Introduction to Algorithms, MIT Press, 2001. – Sahni, Data Structures, Algorithms and Applications in C++, McGraw-Hill, 1998. – Horowitz, Sahni, Rajasekaran, Computer Algorithms, Computer Science Press, 1998.
GIT – Computer Engineering Department
4
Grading Policy: Homeworks Projects Midterm Exam Final Exam
15% 15% 30% 40%
• If your Midterm and Final average is less than 40 out of 100, your letter grade might be less that what your overall average suggests. • If your Midterm and Final average is less than 20 out of 100, you will get a grade of F whatever your overall average is.
GIT – Computer Engineering Department
5
Homework and Project Assignments: Assignments will be announced through the class web site. – All assignments should be submitted on paper before the specified deadline. Late assignments will not be accepted. – You should also submit programming homeworks and projects electronically before midnight of the deadline day. – You should submit at least 80% of the assignments and collect at least 40 out of 100 from the assignments. Otherwise, you will automatically fail. – Assignments will be graded by Teaching Assistants.
Projects and programming assignments will be graded on the basis of – – – –
correctness, quality of design, documentation, and style.
Programming will be done using C++ programming language GIT – Computer Engineering Department
6
Honor Code: Unless stated otherwise, assignments should be done individually and they are expected to be your own work. TAKE PRIDE IN THE WORK YOU DO!!! DON'T CHEAT. You may seek help in identifying syntax and run-time errors and engage in general discussions regarding the solutions, But giving and receiving sections of code will be considering cheating All parties (giving or receiving) will be punished – At least they will get the grade of -100.
GIT – Computer Engineering Department
7
Attendance Policy: Class attendance is mandatory. You will not be able to take the final exam if you miss more %30 of classes. You are responsible for all material covered in class, even when you aren’t there! Attendance for tests and the final exam is mandatory. If it is impossible for you to be present for a scheduled test or exam, you must let us know BEFORE the test, so a make-up test can be scheduled.
GIT – Computer Engineering Department
8
Tentative Schedule: 1
3
Introduction to Software Design: Software life cycle; Managing complexity; Data abstraction; Abstract data types; Program errors and exception; Testing strategies; Program verification. Introduction to Algorithm Analysis: Models of computation; Efficiency of algorithms; Asymptotic notations: O (.), Omega, Teta, o (.); Recursive algorithms; Experimental Analysis. Introduction to Algorithm Analysis: cont…
4
Sequential Containers: The Vector ADT; Implementation of Vector.
5
9
Sequential Containers: Linked Lists; List ADT: List class and Iterator; Implementation List class; Standard Template Library. Stack: Stack ADT; Implementations of Stack class; Applications: Finding palindromes; Testing for balanced parentheses; Evaluating arithmetic expressions. Queue: Queue ADT; Implementations of Queue class; Applications: Simulating physical systems with waiting lines. Recursion: Thinking recursively; Tracing execution of a recursive method; Writing recursive algorithms; Applications; Recursion vs. Iteration. Trees: General structure; Tree traversals; Binary Trees; Binary Search Trees; Implementation of BST.
10
Trees: Heaps; Implementing heaps; Using Huffman trees for compact character storage.
11
Maps and Sets: Map ADT and Set ADT; Hash coding; Open addressing; Chaining; Implementation.
12
Graphs: Terminology; Graph ADT; Implementing Graph ADT; Traversals of Graphs; Topological Sort; Algorithms Using Weighted Graphs: Shortest Path Problem; Minimum Spanning Tree. Self Balancing Trees: Balanced binary search trees: AVL trees; Red-Black trees; Other balanced search trees: 2-3 trees; 2-3-4 trees; B-trees. Sorting: Using STL; Selection sort; Bubble sort; Insertion sort; Shell sort; Merge sort; Heapsort; Quicksort; Performance comparison;
2
6 7 8
13 14
GIT – Computer Engineering Department
9
Class Rules Please be considerate of your classmates during class. Students are expected to show courtesy and respect toward their classmates. Please come to class on time. If you are late wait for the break. Please make sure that your cellular phone and/or pager does not interrupt during lecture time, and especially during test time. Please do not carry on side discussions with other students during lecture time. When you have a question, please raise your hand and ask the question so that everyone may benefit from it.
GIT – Computer Engineering Department
10
Introduction Short introduction to – Data Structures – Algorithms
GIT – Computer Engineering Department
11
What is a Data Structure ? Definition : A representation and organization of data – representation • Determined how a data element is put in the memory – signed, unsigned, etc.
• example : integer representation in memory
– organization • Determines storage scheme of collection of data elements – ordered, inordered, tree
• example : if you have more then one integer ?
GIT – Computer Engineering Department
12
Properties of a Data Structure ? Efficient utilization of medium Efficient algorithms for – creation – manipulation (insertion/deletion) – data retrieval (Find)
A well-designed data structure use less resources – Computational: execution time – Spatial: memory space
GIT – Computer Engineering Department
13
What is An Algorithm ? Definition : A finite, clearly specified sequence of instructions to be followed to solve a problem.
GIT – Computer Engineering Department
14
How to express an Algorithm ? N 3 i Problem : Write an algorithm to calculate ∑ i =1
int Sum (int N) PartialSum 0 i 1
int Sum (int N) { int PartialSum = 0 ; for (int i=1; i<=N; i++) PartialSum += i * i * i;
foreach (i > 0) and (i<=N) PartialSum PartialSum + (i*i*i) increase i with 1 return value of PartialSum
GIT – Computer Engineering Department
return PartialSum; }
15
Properties of an Algorithm Effectiveness – simple – can be carried out by pen and paper
Definiteness – clear – meaning is unique
Correctness – give the right answer for all possible cases
Finiteness – stop in reasonable time
GIT – Computer Engineering Department
16
The Process of Algorithm Development Design – divide&conquer, greedy, dynamic programming Validation – check whether it is correct Analysis – determine the properties of algorithm Implementation Testing – check whether it works for all possible cases
GIT – Computer Engineering Department
17