Flashcards
DSA: Lecture 1
Cards in this deck (34)
- 1What does ADT stand for?Abstract Data Type(s)
- 2Three goals of software engineering?Robustness
Adaptability
Reusability
(RAR) - 3What is Robustness?Program should function properly under all conditions
- 4What is adaptability?Program needs to be able to evolve over time to adapt to current trends
- 5What is reusability?Using the same code as much as possible
- 6Three OO-design principles used in DSA?Abstraction,
Encapsulation,
Modularity.
(AEM) - 7What is abstraction and what does it benefit?Abstraction is taking something complicated (i.e. code) and breaking it down to much simpler forms, but still maintaining the same meaning.
It benefits robustness. - 8What is encapsulation and what does it benefit?Encapsulation is when components should hide internal details from other components (e.g. private variables)
Benefits adaptability of a program. - 9What is modularity and what does it benefit?Modularity is when different parts of a software system should be divided into separate and independent units.
Benefits reusability. - 10What OO-Design TECHNIQUES are used in DSA?Classes and objects,
interfaces,
inheritance and polymorphism. - 11What is a data type?A set of values that the variable can take (e.g. long, char, int, double, etc.)
- 12What are data structures?Collection of variables that are connected and organised in various ways.
- 13What are abstract data types?Mathematical models of data structures together with their operations.
- 14Define an ADTADTs are mathematical models of data structures that specify the types of data stored, operations supported on them and types of operations parameters.
- 15What are ADTs expressed by?Interfaces
- 16What are the three layers of problem solving?Modelling,
Stepwise refinement,
Implementing ADTs. - 17Define an algorithmFinite sequence of instructions, each with a clear meaning, which can be performed in a finite amount of effort and finite amount of time.
- 18What does an algorithm description contain?Inputs and outputs
- 19What are the desired properties for an algorithm?Correctness and efficiency
- 20What is stepwise refinement?Converting an informal algorithm into a formal one
- 21How do insertions and deletions work in stacks?Last in, first out. (LIFO)
- 22Main operations for stackspush(), pop()
- 23What are the auxiliary operations for stacks?top(), size(), isEmpty()
- 24Direct applications of stacksHistory in web-browsers, undo in programs
- 25Indirect applications of stacksAuxiliary data structure for algorithms,
component of other data structures - 26Simple way of implement stack ADTArray where elements are added left to right and a variable keeps track of the index of the top element
- 27Try practicing stack exercisesk
- 28How do insertions and deletions work in a queue?First in, first out.
(Inserted at rear, leave through front)
(FIFO) - 29Main operations of queuesEnqueue(), dequeue()
- 30Auxiliary operations of queuesFront(), size(), isEmpty()
- 31Direct applications of queuesWaiting lists, access to shared resources (e.g. shitter)
- 32Indirect applications of queuesSame as stacks
- 33Queue implementationUse circular array of length N,
have front and rear to keep track,
array location r is kept empty. - 34In multi-programming, what does the term "hanging" mean?When an applet is technically running but not doing anything
Information
- Description
- Flashcards on DSA: Lecture 1, created by krisbraz on 18/03/2015.
- Created by
- krisbraz
- Views
- 4
- Rating