Beginning GATE Computer Science Preparation




— a common problem in many textbook presentations is where the algos are practically used  (looks theoretical)

— suggest students to start with algorithms used in databases ( many practical applications )

— start with basic algorithms in sorting and searching .
— especially merge-sort (will teach about divide&conquer)
— hashing – is used to partition data
— merging – you have two input streams and combine them into a single stream
—  dynamic programming is used for implementing join algorithms

 — some binary tree exercises

1. hashing


— pick a database like mysql (install on ubuntu)
— try designing a simple database – it may be a library management or ticket booking (redbus) or bookstore (flipkart)
— how to arrange data so that it can be efficiently accessed

— what are the entities , relations

— entities in ecommerce(flipkart) – product(book),  customer , order

— relationship – a customer orders a book

—  if data is repeated in multiple places , there is problem of anamolies
— so there is need for normalization

— how  the data is stored on disk.  file organization / btree

—   File structures Book by Michael J. Folk

— Most of the algorithms (binary search tree) were in-memory with random access (accessing any address location)
— whereas in disk , random access is not possible – you have to access sequentially (block by block) – so contiguous storage like arrays is preferred
— so have a combination of  contiguous storage + flexibility of trees
— when data is too large to fit in memory, external sorting algorithms

— codd – instead of nesting data , use relation tuples
— relational algebra simplifies programming (you can reason about it). SQL is a language that implements this relational algebra
— you can learn a bit about optimizing SQL queries. How queries are executed  parse tree of sql query

— C or Java or Python – (python is easy, dynamic typed, interpreted )
— implement few data structures like hashtable or heaps (moderate complexity)
 — implement a finite state machine
— implement a simple Arithmetic expression evaluator

Discrete math+
— CL Liu and Rosen
 —  DM and programming are related in same way as toc and compilers
— to understand the importance of DM, imagine a programmer trying find the names occuring in 2 files
— kiran sir always stresses the importance of discrete
 — Linear algebra
——  polynomials are vectors

— implement a recursive descent parser – take a simple grammar  for evaluating arithmetic expressions
— lex and yacc (from kernighan and pike book)
—  we find there are two ways of approching the problem of parsing — top down vs bottom up
—  when parsing a language (english)- we have these layers –  recognize words , recognize sentences , recognize meaning. similar with parsing a computer langue
— ref

Theory of computation
— it is time to look into more detail about fsm and parsing – fsm didn’t have memory / parsing needs stack. The programs you wrote are called machines (since programs are implemented using them). The input stream you feed into the machine is the language

—  machines and languages

— 4 levels of machines – fsm , pda , lba, turing
— 4 levels of languages  – regular, CFL, CSL, decidable
— finite state machine – the one without memory (useful for embedded systems )
— turning machine – with memory, abstraction of digital computer – computes everything that could be computed.
— halting problem – there are somethings that cannot be computed
— there is a class of problems (equivalent to one another)  that doesn’t have efficient solution
— this leads to problem of studying NP-Completeness
— turing machine
—- FSM
— finite state machines are used in digital logic – gates, counters, registers(memory), ALU,  hardwired control , CPU
— kiran

— memory hierarchy (keep frequently accessed things closer)
— Hamacher
— Digital logic – appendix chapter from Hamacher
— build a computer from first principles
— nand2tetris
— layers build logic-gate / memory / ALU / CPU

— Operating systems abstract the hardware
— different hardware ( intel , arm  ) – each has to be programmed separately
— OS as resource allocator – imagine a university having few classrooms – allocate time / class to teachers without conflicts
— layers – Hardware < OS < Libraries < Application
— Music Player  – different threads run together – one waiting for inputs / one screen refresh
— Producer Consumer – network packets arrive and are processed.  Data is put in  a queue


— memory management –

— Peterson Davie
— Journey of letter via post box goes through layers
— A box for karntaka, a box for dehli – routing at state level won’t worry about inside contents
— Layers each packet

All systems courses are about building layers upon another layer

Polya- How to solve it
Engel – Problem solving strategies
Dromey How to solve it by computer

CS Overview