Advanced Programming Course

1 Introduction
1.1 Common information
1.2 What is an algorithm?
1.3 What is a program?
1.4 Data structures
1.5 Why do we need various data structures?
1.6 Reminding the terms used
1.7 Basic programming techniques
2 Reminding C
2.1 Basic C Programming
2.1.1 C Program Structure
2.1.2 Variables
2.1.3 Arithmetic Operations
2.1.4 Comparison Operators
2.1.5 Logical Operators
2.1.6 Order of Precedence
2.2 Conditionals
2.2.1 The if statement
2.2.2 The ?: operator
2.2.3 The switch statement
2.3 Looping and Iteration
2.3.1 The for statement
2.3.2 The while statement
2.3.3 The do-while statement
2.3.4 break and continue
2.4 Arrays
2.4.1 Single and Multi-dimensional Arrays
2.4.2 Strings
2.5 Exercises
2.6 Functions
2.6.1 void functions
2.6.2 Functions and Arrays
2.6.3 Function Prototyping
2.7 Further Data Types
2.7.1 Structures
2.7.2 Defining New Data Types
2.7.3 Unions
2.7.4 Coercion or Type-Casting
2.7.5 Enumerated Types
2.7.6 Static Variables
2.8 Common Mistakes in C
2.8.1 Assignment (=) versus Comparison (==)
2.8.2 Missing () of a function
2.8.3 Array indices
2.8.4 C is Case Sensitive
2.8.5 Semicolons end every statement
2.9 Pointers
2.9.1 What is a Pointer?
2.9.2 Pointer and Functions
2.9.3 Pointers and Arrays
2.9.4 Arrays of Pointers
2.9.5 Multidimensional arrays and pointers
2.9.6 Static Initialization of Pointer Arrays
2.9.7 Pointers and Structures
2.9.8 Common Pointer Pitfalls
2.10 Dynamic Memory Allocation
2.10.1 Malloc
2.10.2 Linked Lists
2.11 Input and Output (I/O)
2.11.1 Streams
2.11.2 Basic I/O
2.11.3 Formatted I/O
2.11.4 Files
2.11.5 sprintf and sscanf
2.11.6 Command line input
2.12 Low Level Operators
2.12.1 Bitwise Operators
2.12.2 Bit Fields
2.13 The C Preprocessor
2.13.1 #define
2.13.2 #undef
2.13.3 #include
2.13.4 #if - Conditional inclusion
2.14 ANSI C Library
2.15 Exercises
3 Linked List
3.1 The simplest operations on list. Iterative and recursive algorithms.
3.2 Running time of insertion to non-ordered list; insertion to ordered list.
3.3 Selection sorting.
3.3.1 Abstract of the algorithm.
3.3.2 Use of selection sort for array of integers.
3.4 Algorithm paradigm "Divide-and-Conquer".
3.5 Merge sorting.
3.5.1 Dividing of list to sub-lists.
3.5.2 Merging of ordered lists.
3.6 Quick Sort
3.7 Other sorting algorithms
3.8 Exercises
4 Stack and Queue
4.1 Stack
4.1.1 Set of operations.
4.1.2 Implementation with linked list.
4.2 Queue
4.2.1 Operations on queue
4.2.2 Implementation with double-linked list
4.3 FIFO and LIFO approaches. Their importance.
4.4 Exercises
5 Trees
5.1 Examples of trees.
5.2 Advantages of trees
5.3 Formal definition of trees
5.4 Operations on trees
5.5 Various types of trees and tree implementations
5.6 Binary trees
5.6.1 Search in B-tree
5.6.2 Insertion of a node to B-tree
5.6.3 Deletion of a node from B-tree
5.6.4 Balanced trees. AVL trees
5.7 Exercises
5.8 Not binary trees
5.8.1 Children vector (Array-of-Pointers)
5.8.2 Trie
5.8.3 Sibling
5.9 Traversing tree
5.9.1 Preorder
5.9.2 Postorder
5.9.3 Inorder
5.10 Important tree applications
5.10.1 Expression trees
5.10.2 Syntax trees (Parse trees)
5.10.3 Decision making trees
6 Graphs
6.1 Examples of graphs
6.2 Formal graph definition. Kinds of graphs
6.3 Graph implementations
6.3.1 Adjacency lists
6.3.2 Adjacency matrices
6.3.3 Comparison of the implementations
6.4 Operations on graphs
6.4.1 Graph traversing
6.4.1.1 Breadth first search and traversal
6.4.1.2 Depth first search and traversal
6.4.2 Exercises
6.4.3 Applications of the graph traversing
6.4.3.1 Connected components find
6.4.3.2 Reachability test
6.4.3.3 Topological sort for non-directed acyclic graphs
6.4.3.4 Minimal spanning tree find (Kruskal's algorithm)
6.4.3.5 Shortest path find (Dijkstra's algorithm)
6.4.3.6 Clique find. NP-complete problems
6.5 Important graph applications