MSI CircuitsMinterm=> Multiplication of the terms (ie x.y)Maxterms => Addition of terms (ie x+y)Decoder (n*m)Selects n input and have m outputRepresent up to 2^n unique elementsm < =2^nOutput will just high to the binary that is connected to the input.Internal WiringThe output of the decoder corresponds to minterms.We can use the...
[Read More]
CS2040s: MST (Minimum Spanning Tree)
Minimum Spanning TreeA spanning tree is a acyclic subset of the edges that connects all nodes.A minimum spanning tree is a spanning tree with minimum weightThe weight is the sum of all the weights of all the edges in the tree.Can we use MST to find shortest paths? Nope=> Shortest...
[Read More]
GES1011: Lecture 8 - Decolonisation
RecapImperialism: Best explains global power relations from around 1750s to 1945.WW1 and WW2 is war of empires, if we did not follow, we will be bullied into following our empire overlord.Japanese Surrender:News reported that 100000 locals residents of singapore greeted this event rapturously.Remembered differently by different party.Encompassing apologies, reparation and...
[Read More]
CS2100: Combinatorial circuits
Combinational circuitDepends on the immediate inputSequential CircuitEach output depends on both present inputs and state.Analysis Procedures1.Label input/output2. Obtain the functions of immediate points and output3. Draw truth table4. Deduce the functionalityDesign methodsGate- level designwith logic gatesBlock-level designWith functional blockMain Objectives- Reduce cost- Increase speed- Simple designsDesign Procedure1. State problem2. Determine...
[Read More]
CS2100: Simplification
SimplificationTo get simpler expression for fewer logic gate.-> CheaperAlgebraicUse theoremsOpen ended requires skillsAims:- Reduce number of literals- Reduce number of termsSometimes these conflict, reducing one does not mean reduce the otherFocus on reduce literals by using the laws.K-MapEasy to useLimited to no more than 6 variablesBut we need truth table:Make...
[Read More]
CS2040s: All Pairs Shortest Paths (APSP) + Revision
Floyd WarshallComputes the distance between all Pairs of nodesKey ideas: Shortest path have optimal substructureAll subpath of the shortest path is the shortest pathDynamic Programming1. Figure out the subproblems2. Relate the subproblem solutions3. Recurse and memorise4. Solve the original problem via subproblemsOptimal Sub-structureThe optimal solution can be constructed from optimal...
[Read More]
CS2040s: Shortest path (Special Cases)
RecapSimple pathThere are no cycles, if a graph contains no negative weight cycles then the shortest path is a simple path whereit has at most v - 1 edgesShortest PathMaintain estimate for each distance: Relax(s,B)Update the current shortest path when a shorter path is found(relax)The subpath of shortest path are...
[Read More]
GES1015: Lecture 7 - The occupation
Occupation of an Imperial Power"What was there in so call asia before the european appears?" There were already imperialism in Asia, kingdoms that conquered many landThe use of imperial power is use control and to exploit others. Why do we consider Japanese's arrival as the Japanese occupation of singapore? Isn't it just...
[Read More]
ES2660: Wild Card #6 Articulation and Eloquence
Articulation and Eloquence#2- Inform audience- Encourage them- One must be clear on what they are talking about and be able to articulate what they are talking about- need content enough to be able to talk about the topic- Supporting gestures like hand gestures and eye contact also help in articulation.#3- Two...
[Read More]
CS2040s: Tutorial 8
BFSTime - o(V + E)Space- o(V)The queueDFSTime - O(V + E)Space - O(V)The stackBFTime - O(VE)Space - O (V)Store the cost it takes to get every verticeQ1a) DFS Back and Forthb) Do two bfsOne on original graph and the other on flip graphO(2(V+E))Space: O(V+E)Q2a)Use BFS to find Naruto and to...
[Read More]
CS2100: Performance and ISA General Concepts
Performance and ISA General ConceptsResponse: Number of seconds per instructionPerformance: Number of instruction per one secondWe can use this for pipelineAverage CPICPI = sum of (cycles for each instructions * F)F = instruction Freq / Instruction CountCPI = (CPUtime * Clock Rate) / Instruction Count= Clock Cycles / Instruction CountInfluencing...
[Read More]
CS2100: Boolean/Logic Gate
Boolean AlgebraDigital Circuit- Reliable- More accurate- Represented in math- Ease of designBasic operation- Not - And (A ^ B)- Or (A V B)Not > And > OrLAWS:DualityWe can interchange the + and X in all formula and it will still remain the sameIts two for one.If there are any elements inside,...
[Read More]
CS2040s: Discussion Group 8
RECAPBFS - Find neighbours firstDFS - Go as far as possible (Stack)Kahn's algorithm1. Keep removing each time we go down the list2. After each removal, append to the list3. Final result topologicalBut the sort is not unique
CS2040s: Single-Source Shortest Path for graphs
Single Source Shortest PathWeighted Graphw(e) : E -> REach edge have a weight.Shortest PathShortest path is not the minimum distance- What is the path from a certain node to another?- Shortest path from a node to every other node?- Shortest path between every pair of nodeWe cant use BFS because...
[Read More]
CS2040s: Searching On Graphs
Searching.. Graph EditionGoals:Starting at some vertex s and find some other vertex f (finish)Visit all nodes in the graphTechniquesBreadth first Search (BFS)Explore level by level.Always moving forward in the frontier (wave)Initial = {s}Do not go backwards => Find the shortest pathUses a QueueWe keep looking at the neighbours at selected nodes...
[Read More]
Lecture 6: Life, society and classification
Making sense of life and society in Singapore in the middle years of British colonialism.Thinking about it..Just because we have a world with fix boundaries. The ramification are potential endless and the number of imperial context are numerous. We must appreciate that colonialism include militaries, the traders and clergy.The people...
[Read More]
GES1011: Reflection on History Museum
This is my reflection regarding the trip/visit and my critique against/with the museum.Choice of Museum: Singapore Marinetime GalleryLocation: Marina Coastal DriveDate went: Friday afternoonPictures:My first impression of this museum is that it is very quiet, there is not a lot of people there. Also if it is to be taken...
[Read More]
CS2040s: DG 4
HashsetImagine we are taking inventory and we want to check what types of fruits is in the house so we add the differnt fruits into the hashset. We are not concern how many there are but more of the existenceHASHMAPLests imagine we have an inventory checklist, we want to add...
[Read More]
CS2040s: Introduction To Graphs
GraphsGraphs are a couple denoted by G={V,E} (a tuple of two sets)where V is the set of vertices and E is set of EdgesVertices is the nodesEdges are the path connected the nodesSimple graphs=> A node cannot have edges pointing at itself => only one edge per pair of nodes.Connected Graphs=>...
[Read More]
CS2100: Cache
CACHEDirect MappedNon-volatile Memory- Storage that maintain information even without power- ROM (Read - only memory)- Store persistent information like fileVolatile- Loses information when electrical power is interrupt- RAM (Random Access Memory)- Main storage of Process Memory discussedDram- Stores a single Bit- High density- Can pack a lot together to form...
[Read More]