Data structures & Algorithms
What is a Graph? how highly connected is an entity within a network? What is an entity's overall importance in a network ?
INSTRUCTIONS TO CANDIDATES
ANSWER ALL QUESTIONS
What is a Graph?
- A graph is a data structure representing connections between items
- We're storing values with the potential for connections between any or all elements
- Examples of graphs in everyday life:
- Examples in computer science
- Networks
- Social Network diagrams
- Executing a makefile
Social Networks
Using Social Network Analysis, you can answer:
is an entity within a network?
overall importance in a network?
- How central is an entity within a network?
- How does information
flow within a network?
Makefiles
How make Works
- Construct the dependency graph from the target and dependency entries in
the makefile
- Do a topological sort to determine an order in which to construct
- For each target visited, invoke the commands if the target file does not exist or if any dependency file is newer
- Relies on file modification
dates
Set Theory
- A set is any collection of objects, e.g. a set of vertices
- The objects in a set are called the elements of the set
- Repetition and order are not important
- {2, 3, 5} = {5, 2, 3} = {5, 2, 3, 2, 2, 3}
- Sets can be written in predicate form:
- {1, 2, 3, 4} = {x : x is a positive integer less than 5}
- The empty set is {} = 0, all empty sets are equal
Elements and Subsets
- x ∈ A means “x is an element of A”
- x ∈ A means “x is not an element of A”
- A ⊆ B means “A is a subset of B”
- x ⊆ A means “x is not a subset of A”
A is a proper subset of B and we write A ⊂ B
- A ⊆ A for every set A
- Every set is a subset of itself
Subsets
- If A ⊆ B and B ⊆ C then A ⊆ C
- If A ⊆ B and B ⊆ A then A = B
- The empty set is a subset of every set:
∅⊆ A for any A
- The subsets of A ={1, 2, 3} are:
∅,{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
(Sometimes called the powerset of A, P(A) )
Operations on Sets
- Union
- A ∪ B = { x : x ∈ A or x ∈ B }
- Intersection
- A ∩ B = { x : x ∈ A and x ∈ B }
- Universal Set
- All sets under consideration will be subsets of a background set, called the Universal Set, U
- Complement
- A' = { x : x ∈ U and x ∈ A }
Example
- Let:
- U = {a, b, c, d, e, f}
- A = {a, c}
- B = {b, c, f}
- C = {b, d, e, f}
- Then:
- B ∪ C = {b, c, d, e, f}
- A ∩ (B ∪ C) = {c}
- A' = {b, d, e, f}
= C
- A' ∩ (B ∪ C) = C ∩ (B ∪ C) = {b, d, e, f} = C
Related Questions
. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java
CS 340 Milestone One Guidelines and Rubric
Overview: For this assignment, you will implement the fundamental operations of create, read, update,
. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class
Retail Transaction Programming Project
Project Requirements:
Develop a program to emulate a purchase transaction at a retail store. This
. The following program contains five errors. Identify the errors and fix them
7COM1028
Secure Systems Programming
Referral Coursework: Secure
. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer
CS 340 Final Project Guidelines and Rubric
Overview The final project will encompass developing a web service using a software stack and impleme