Advanced Programming Course
Contents
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.2.1 Defining Global Variables
2.1.2.2 Printing Out and Inputting 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 Exercise 1
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.9.8.1 Not assigning a pointer to memory address before using it
2.9.8.2 Illegal indirection
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.1.1 Predefined Streams
2.11.1.2 Redirection
2.11.2 Basic I/O
2.11.3 Formatted I/O
2.11.3.1 printf
2.11.3.2 scanf
2.11.4 Files
2.11.4.1 Reading and writing 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.14.1 Buffer Manipulation
2.14.2 Character Classification and Conversion
2.14.3 Data Conversion
2.14.4 Directory Manipulation
2.14.5 File Manipulation
2.14.6 Input and Output (Stream I/O)
2.14.7 Mathematics
2.14.8 Memory Allocation
2.14.9 Process Control
2.14.10 Searching and Sorting
2.14.11 String Manipulation
2.14.12 Time
2.15 Exercise 2
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.3.2.1 Iterative version.
3.3.2.2 Recursive version.
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 Exercise 3
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 Exercise 4
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.6.4.1 Disadvantages of simple B-trees. The main idea of balanced trees.
5.6.4.2 The main idea of the AVL algorithm.
5.7 Exercise 5
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 Exercise 6
6.4.3 Applications of the graph traversing and other important algorithms on graphs
6.4.3.1 Connected components find
6.4.3.2 Reachability test
6.4.3.3 Topological sort for undirected 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 tasks
6.5 Important graph applications
Apeendix A Examination Question Examples