Beginning GATE Computer Science Preparation

Ad Blocker Detected

Our website is made possible by displaying online advertisements to our visitors. Please consider supporting us by disabling your ad blocker.

 

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 Reply