/Alg_dstr_c

Primary LanguageC

Algorithms and Data Structures in C

Note:

  • learning for different books and online resources made me realize that allot of these learning reasources either don't provide complete and correct implementation. So best choice is to be reading through a couple of them at the same time.

  • Read/watch a couple of sources at the same time for the same topic

  • Read the chapter first and try to implement it with out looking, and look only when stuck.

MEMORY: ALWAYS MAKE SURE ALL VARIABLES ARE INITIALIZED TO 0 OR NULL!!!! ALWAYS!!!! Use calloc where applicable. memset to 0 and so on

Array:

Array also correspond directly to vectors, the mathematical term for indexed list of objects. Two-dimentsional arrays correspond to matrices. src

  • Find Median
  • Find Max Min "find_max_min(" Search:
  • Binary Search
  • Max sub array

Sorting Algorithms:

Sorting

Searching

  • backtracking
  • sorting
  • depth-first search & breadth-first search (graphs)

String:

  • String with Reverse Polish notation/postfix to stack
  • remove char from string
  • check anagram
  • find duplicate characters
  • string size
  • check palindrome
  • reverse array

Data Structures / Abstract Data Types

Reading Searching Insertion Deletion
Array O(1) O(N) O(N) or O(1) at the end O(N) or O(1) at the end
Array Ordered O(1) O(log N) O(N) O(N)
Hash Table O(1) O(1) O(1) O(1)
Linked List O(N) O(N) O(N) or O(1) at the begining O(N) or O(1) at the begining
Doubly Linked List O(N) O(N) O(1) O(1)
Binary Tree O(N) O(log N) O(log N) O(log N)
Graph - O(1) - -
stack
queue
set

Operations:

  • Initialize the data structure
  • Search for a record (or records) having a given key.
  • Insert a new record
  • Delete a specified record
  • Join two dictionaries to make a large one
  • Sort the dictionary; output all records in sorted order
  • Modify

Implemented:

Practical Aplications:

Dynamic Programming

  • Basic
  • Advanced

Cryptography

Math and Numbers

  • numbers
  • Number Theory
  • Counting
  • Geometry

Reusability

  • How to build reusable data types and algorithms in C? tree.h in freebsd. It implements functions inside some long macros. Before calling these functions, you need to instantiate them with proper types. This style is closer to C++ template and incurs little overhead in the sense that it can achieve the same performance as a type-specific implementation. This is my preference.

list.h in Linux kernel. It embeds a predefined struct to the struct holding the actual data. Here is an example program. uthash follows a somewhat similar route, though it uses much more macros.

avl.c from libavl and Glib. It uses void* pointers to represent generic data types. I don't like this approach personally because it often hurts performance. However, many others hold different opinions.

  • Check out the book "C Interfaces and Implementations". It has a lot of good ideas and practices.

Sources:

  1. [Book] The C Programming Language 2nd Edition by Brian Kernighan and Dennis Ritchie
  2. [Book] Wengrow Jay - A Common Sense Guide to Data Structures and Algorithms
  3. [Book] Algorithms in C by Robert Sedgewik
  4. [Book] Algorithms by Robert Sedgewik, Kevin Wayne. Fourth edition. 459
  5. [Book] "Data Structures and Algorithms in Java" by Goodrich M., Tamassia R., Goldwasser M.
  6. https://github.com/jamesroutley/write-a-hash-table

Todo:

  • swap variables on memory, not array
  • redo Max Min
  • redo Stack
  • recursion stuff

todo: