Beginning GATE Computer Science Preparation

 

ORDER OF COVERING TOPICS

ALGORITHMS
— 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

references
1. hashing https://www.youtube.com/watch?v=AfKV7YXGY-I


DATABASES

— 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


PROGRAMMING
— 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
— http://www.programmingbasics.org/en/beginner/fsm.html
— 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 https://www.youtube.com/watch?v=xhTciBubSfM

Compilers
— 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 http://www2.gvsu.edu/boucharj/Prog1.c

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
[References]
— turing machine https://www.youtube.com/watch?v=dNRDvLACg5Q
—https://www.youtube.com/watch?v=Pt6GBVIifZA
— https://en.wikipedia.org/wiki/Chomsky_hierarchy
—- FSM http://www.inf.ufsc.br/~joao.dovicchi/pos-ed/pos/exerc/machines2.pdf
— finite state machines are used in digital logic – gates, counters, registers(memory), ALU,  hardwired control , CPU
— kiran https://www.youtube.com/watch?v=8S9MMsaUMg4

architecture
— memory hierarchy (keep frequently accessed things closer)
— Hamacher
— Digital logic – appendix chapter from Hamacher
— build a computer from first principles
— nand2tetris   https://www.youtube.com/watch?v=iE7YRHxwoDs
— layers build logic-gate / memory / ALU / CPU

OPERATING SYSTEMS
— 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
— http://www.iu.hio.no/~mark/os/

— www.cs.huji.ac.il/course/2010/os/notes/os-notes.pdf

— memory management – https://www.youtube.com/watch?v=lEG71DDLD9E


NETWORKS
— 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

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

CS Overview
https://www.linkedin.com/groups/8345172

Leave A Comment