Friday, 2 December 2016

15 Tips for Filming and Editing Marketing Videos

Lately, I haven’t been blogging as much here at WordStream. I haven’t been on an extended road trip (sob), nor have I spent the last eight weeks or so in quiet contemplation in a monastery atop a mountain in the Himalayas (though I could definitely use it).
The reason I’ve been blogging a lot less than usual is because I’ve been working on some exciting side projects here at WordStream, namely shooting and editing a lot of video (stay tuned in the coming weeks for more info).
 Editing marketing videos professional video shoot
Many marketers want to get into video, but to say it can be intimidating would be an understatement. With so much to think about – from camera equipment and editing software to lighting a shot and optimizing audio – the barriers to entry can be high. Fortunately, the price of decent gear and post-production software has dropped significantly during the past 10 years, making now the ideal time to start producing your own marketing videos.
In today’s post, I’m going to share 15 tips for editing and producing marketing videos, so grab a cup of coffee and get ready for a crash course in marketing video production.

Marketing Videos: Pre-Production

1. Create a Storyboard and/or Shooting Script

The best marketing videos don’t just happen – they’re a result of meticulous planning and preparation.
Before you even think about getting your camera equipment ready, consider putting a storyboard and shooting script together. Storyboarding helps you figure out exactly what shots you need before you start filming, and a shooting script is like a screenplay for your video.
 Editing marketing videos Harry Potter storyboard
Storyboard panels for ‘Harry Potter and the Deathly Hallows, Part 2’
You don’t have to draw a stunning masterpiece for your storyboard. In fact, you don’t need to draw it at all. You can use a series of still photographs as a storyboard, or even rough sketches or stick figures – whatever is easiest. Just make sure you know what shots you need before you start filming.
Remember – the more time you spend planning your marketing video, the less likely you are to find yourself missing footage later on.

2. Prep Your Presenters or Interview Subjects

Make sure all your presenters or subjects know what’s expected of them beforehand to minimize mistakes or wasted time on the day of the shoot. You should have a good idea of what the finished product is going to look like long before you arrive at your location, and your presenters should know exactly what they’re doing.
Also, try to avoid having your presenters memorize pages upon pages of script – they’re probably not actors, and asking this of them is likely to cause more anxiety (and mistakes) than allowing them a little freedom.

3. Know What B-Roll Footage You Need

Planning to intersperse shots of your team hard at work into your video, or cut away from your presenter to other footage? Then you need what videography professionals call B-roll footage.
B-roll is essentially any footage that isn’t of your primary subject. If you’re filming an explainer video showcasing your software product, B-roll footage might include shots of satisfied customers using your product, or an external shot of your offices, for example.
Whatever footage you need, figure it out during the pre-production phase to avoid situations in which you need footage you don’t have. Remember – there’s no such thing as too much B-roll.
TIP: If you need a shot of something that would be difficult or impossible to film yourself, such as aerial shots or footage from exotic locales, you can always use stock B-roll footage. I’ve used footage from Beachfront B-Roll several times in the past, and the quality and diversity of the footage is excellent.

Marketing Videos: Production

Whether you’re shooting a video or taking a photograph, composition is crucial to the finished product. Composition is so important it deserves a post in and of itself. However, since this is a crash course, we’ll just cover the basics for now.
Composition is the proper term for how a shot is framed and staged, or “composed.” This refers to how your subject – whatever it is you’re filming – is arranged and positioned within the shot.

4. Use the Rule of Thirds

Whenever you’re filming anything (or taking photos), remember the “Rule of Thirds.”
Imagine your shot is divided into nine equal sectors by two horizontal lines and two vertical lines, like so:
 Editing marketing videos Rule of Thirds principle
Notice how the primary subject in the image is positioned where two of the four points (which are known as the “anchor points”) intersect? This technique is used to draw the eye toward the main points of interest in the shot. The viewer’s eye will naturally gravitate towards the top-left anchor point, and many people will spend longer dwelling on this area than other parts of the shot, making it a logical point at which to position the main area of interest in your shot – in this example, the face of the subject.
This is a pretty standard composition using the Rule of Thirds, and although it might not seem that remarkable, composing your shot in this way makes it easier for the eye to “read” and results in a much more aesthetically pleasing shot overall. Your audience probably won’t even notice the composition of the shot, because it just “works.”
The Rule of Thirds can be applied to just about any type of shot, including landscapes. Using the horizontal lines is a great guide for where the horizon line of your exterior shots should be, and where your subject should be positioned:
 Editing marketing videos Rule of Thirds applied to landscape
In the example above, the upper of the two horizontal lines is the logical horizon point for this shot, as using the lower of the two would result in the shot containing way too much empty sky. Of course, this might be precisely the effect you’re trying to achieve, so think of this as a guideline rather than a hard-and-fast “rule.”
Many cameras enable you to overlay this grid onto your viewfinder, making it easy to compose your shot before and during filming.
However you choose to frame your shot, make sure that you keep composition in mind, especially when setting up your camera. To read more about shot composition, check out this great guide to line, shape, negative space, and other composition techniques.

Marketing Videos: Lighting

Few things will ruin a marketing video faster than a shot that is either too light or too dark. Yes, you can correct image brightness and contrast in post-production to some extent (more on this later), but it’s better to get the shot right on the day of the shoot than relying on “fixing it in post” later on.

5. Avoid Conflicts Between Natural and Artificial Light

When it comes to lighting in video, different kinds of light have different temperatures. These color temperatures are measured in degrees Kelvin (°K):
 Editing marketing videos color temperature chart
Again, this is a complex topic and could easily warrant its own post, but for our purposes, all you need to know is that mixing two light sources with different color temperatures will make for an unevenly lit shot.
Let’s say you’re shooting an explainer video featuring a member of your team. You’ve chosen an indoor room with good acoustics (more on this later), and you’re ready to start filming. The room is lit primarily by fluorescent lights, but there’s a problem – a large window that lets in plenty of natural daylight.
If you position your subject too close to the window, you could run into a potential contrast in light sources – the fluorescent overhead light with a temperature of around 4500° K, and the daylight, which has a temperature of around 5600° K. This kind of conflict can be difficult to compensate for, and it’s a headache you really don’t need.
Wherever you’re shooting, ensure that your primary light source is even and consistent. If you shoot indoors, avoid rooms with windows. If this isn’t possible, position your subject sufficiently far from the windows to avoid the daylight interfering with your shot.

6. Manually Set Your Camera’s White Balance

Now we know that different light sources have different temperatures, we need to account for these temperature ranges by manually setting the camera’s white balance – a process that basically tells the camera what “true white” looks like in an environment to avoid color casting.
 Editing marketing videos white balance example
In the image above, the shot on the left has a blue color cast caused by the natural temperature of the daylight in the shot. The white balance of the shot on the right has been set correctly, capturing the true colors of the image.
Many cameras have an auto-white balance feature, but I strongly recommend learning how to set it manually. This avoids relying on your camera to achieve a correctly color balanced shot. You can learn how to do this by referring to the instruction manual of your camera.
Even if the color casting in the example above is the effect you’re trying to achieve, film the shot using the correct white balance and adjust the color in post-production – don’t rely on lazy camerawork to achieve a particular effect.

7. Avoid ‘Spotlighting’ Your Subject

Unless you’re filming a Broadway musical, you should probably avoid placing your subject in bright pools of direct light. Intense primary light sources can blow out the brightness and contrast of your shot and cause unflattering reflections on your subject. There are many different lighting techniques, each of which can be used to achieve a certain effect.
 Editing marketing videos lighting setup examples
If you’re lucky enough to have a professional light rig, don’t just point it at your subject – make sure your shot is lit evenly, and use a reflector and/or a diffuser to minimize harsh spotlighting or shadows (such as the “mustache” in the far-left example above).
To learn more about lighting for video, check out the awesome videos at the Vimeo Video School.

8. Check the Acoustics of Your Filming Location

Before you start filming, check the acoustics of the location in which you’re shooting. Is there an echo? If so, try and find somewhere else to shoot. You can fix a lot of audio problems in post-production, but even a faint echo can be a nightmare to get rid of completely.
You don’t need to soundproof a conference room in your office (but hey, if you can, go for it), but be sure to bear the acoustics of your location in mind when you’re scouting for possible places to film. It could save you a lot of headaches later.

9. Shoot Multiple Takes

Even experienced presenters make mistakes, and the last thing you want is a situation in which you only have a single take of a crucial part of your marketing video.
 Editing marketing videos Avengers blooper gif
Even Norse gods mess up sometimes.
On the day of the shoot, make sure to run through multiple takes. This provides you with a safety net in case you notice something wrong with one of the takes, and allows you to edit together your final sequence from several clips of the same sequence rather than relying on just one.
Even if the first take goes flawlessly, shoot another – just in case.

Marketing Videos: Post-Production

Before we dive into my post-production tips, you need to choose and familiarize yourself with your editing software.
I strongly recommend using Adobe Premiere Pro, which has been my go-to editing package for almost a decade. This remarkably robust editing program has everything you need to start producing professional-quality marketing videos, and the pricing plans are very reasonable (around $250 per year for an individual license), meaning that the barriers to entry have been lowered considerably, even for small businesses.
Despite being a comprehensive professional editing suite, Adobe Premiere Pro is also surprisingly user-friendly, and the learning resources and user community at the Adobe website are amazing.
If you’re working on a Mac, you might be tempted to opt for Apple’s Final Cut Pro. Although Final Cut Pro is a fine editing package, I still recommend using Premiere Pro. In my opinion, the ease with which you can seamlessly move between Premiere Pro and other Adobe programs such as After Effects and Photoshop alone makes it the stronger software program.

10. Tidy Up Your Clips Before You Start Assembling the Rough Cut

When importing your footage into your editing program, clean up your clips as you import them. Most editing packages allow you to set “in” and “out” points for each clip, reducing their length by trimming out pauses, giggles, and false starts.
Editing the final sequence together using trimmed clips is a lot easier than adjusting each individual clip on the fly.

11. Always Cut ‘On the Action’

When editing a shot of someone doing something, make sure to cut to the next shot during the action that your subject is performing.
For example, if you’re editing together a sequence of someone opening a door before walking through it, cut to the shot of the subject opening the door at the precise moment the person turns the door handle. Cutting away before or after the action can look jarring and distract the viewer. You may not even have to worry about this, but it’s worth bearing in mind if you’re working on a more ambitious video.

12. Assemble the Rough Cut Before Working Out Any Timing Issues

Once you’ve got all the clips you need imported into your editing program, it’s time to start actually putting the rough cut of your marketing video together.
 Editing marketing videos editing tips
Editing a sequence can get complicated quickly, so tidy up your clips as you work.
However, before you begin the painstaking process of frame-by-frame editing, get your clips roughly into place. There’s no point agonizing over precise timing issues until your video has already begun to take shape. It won’t look pretty, but it’ll give you a solid idea of which parts of your marketing video need the most work.

13. Don’t Overdo It with Transitions and Effects

Unless you’re making a Star Wars parody video (which would be kind of awesome in a marketing context), don’t use radial wipe transitions – or star wipes, or any of the other “zany” effect presets that come with your editing software. The more attention to draw to your transitions and editing, the cheaper and more amateurish your video will look (and yet we still forgive George Lucas for this).
If you have to, use simple cross-fades to transition from one shot to another. Let your content do the talking, not your editing software.

14. Choose Your Music Carefully

Not every video needs background music, but if you’ve decided that yours does, be careful about your choices. For example, you probably wouldn’t expect to hear Norwegian death metal in a promotional video for an animal shelter. Ensure your music is suitable for your project.
 Editing marketing videos music piracy
Also, pay close attention to the licensing requirements of the music you plan to use. Unless you use royalty-free music or compose your own, most music is subject to stringent copyright restrictions that could land you in some seriously hot legal water if you don’t play by the rules.
Remember – a record company won’t care if you’re “only” using copyrighted songs in a short marketing video. It’s copyright infringement, plain and simple, and it could result in a costly lawsuit, so tread carefully and err on the side of caution.
TIP: There are several sites that offer royalty-free music and sound effects, including:
You can also use certain songs and orchestral pieces if they are considered to be within the public domain. You can read more about public domain music at the Public Domain Information Project, and browse a selection of public domain artists and genres at Public Domain Music.

15. Don’t Assume You Can Fix Everything in Post-Production

Editing packages such as Premiere Pro and Final Cut Pro are extraordinarily powerful and enable you to accomplish a great deal with your videos, but they’re not magic.
Don’t assume that any and all problems with your video can be fixed in post-production. Sometimes, you simply won’t be able to correct the brightness or contrast of a shot as much as you need to, or manage to isolate a single person’s voice in a room crowded with hundreds of people. Yes, it might be possible given enough time and skill, but post-production should be seen as a process to add polish and finesse to your video, not an opportunity to go back and fix mistakes that could have been easily avoided during a properly planned shoot.

And … Cut!

Hopefully, this post has given you some ideas of pitfalls you can avoid when the time comes to start producing your own marketing videos.
If you have questions about any of the points raised or anything else video-related, let me know in the comments – I’ll do my best to answer them.
Happy shooting!

Monday, 17 October 2016

How is GST Different from Current Tax Structure


What does this mean? What will be its impact?
GST proposes to remove the geographical barriers for trading, and transform the entire nation to ‘One Common Market Place’.
Let us understand the fundamentals of GST, it is a dual concept tax system. Under this system, tax is administered, collected, and shared by both the Centre and the State governments, based on the nature of transaction (within the state or interstate).
The tax components of GST 


While we now know the tax components of GST, it is equally important for you to know the taxes existing in the current regime, and how they are subsumed under GST.
Current Indirect Tax structure
Current Tax structure Vs GST

Taxes subsumed under GST

Sunday, 16 October 2016

What Can You Do With a Graphic Design Degree?

what can you do with graphic design degree
The road to achieving career success looks different for everyone. After some thought, you’re starting to realize that pursuing a degree in graphic design might be the right path for you. But before you commit the time and money it takes to acquire a formal education, you want to know what your job prospects will look like after graduation.
So what can you do with a graphic design degree, anyway?
Most people think there is a single answer: become a graphic designer, of course! But the truth is that the options are much more vast than that! The bulk of learning the trade is focused on design concepts and skills but there are still a host of non-design skills you’ll need to learn if you want to be successful in the field. Once you master those skills, your graphic design career options will begin to unfold before your eyes!

10 careers for graphic design degree holders

We used real-time job analysis software from Burning-Glass.com to examine more than 7,500 job postings calling for candidates with a graphic design degree.* Below you’ll find a breakdown of the 10 most common positions we identified in our analysis.
The information included will provide you with an accurate picture of what each job entails, including the outlook and average earning potential for all.** Click each job title for a more in-depth look from the U.S. Department of Labor.

1. Graphic designers

  • Develop graphics and layouts for product illustrations, company logos and websites
  • Review final layouts, suggest improvements if needed and make necessary changes
  • Maintain archive of images, photos and previous work samples
Median annual salary: $44,830
Projected growth (2012-2022): 7 percent

2. Web developers

  • Use authoring or script languages and managing tools to design, build and maintain websites
  • Evaluate code to ensure that it is valid, is properly structured and meets industry standards
  • Identify and correct problems uncovered by testing or user feedback
Median annual salary: $63,160
Projected growth (2012-2022): 20 percent

3. Art directors

  • Confer with clients to determine objectives, budget, background information and presentation approaches
  • Work with department heads to discuss client requirements and presentation concepts and to coordinate creative activities
  • Work with creative directors to develop design solutions
Median annual salary: $83,000
Projected growth (2012-2022): 5 percent

4. Multimedia artists/animators

  • Design complex graphics and animation using computer animation or modeling programs
  • Apply story development, directing, cinematography and editing to animation
  • Develop briefs, brochures, web pages, promotional products and technical illustrations for use in products and manuals
Median annual salary: $64,470
Projected growth (2012-2022): 6 percent

5. Marketing specialists

  • Collect and analyze data on customer demographics, preferences, needs and buying habits
  • Gather data on competitors, analyzing their prices, sales and method of marketing distribution
  • Measure the effectiveness of marketing, advertising and communications programs and strategies
Median annual salary: $60,800
Projected growth (2012-2022): 22 percent

6. Software quality assurance testers

  • Design test plans, scenarios, scripts or procedures
  • Identify, analyze and document problems with program function, output, online screen or content
  • Participate in product design reviews to provide input on functional requirements, product designs, schedules or potential complications
Median annual salary: $83,340
Projected growth (2012-2022): 7 percent

7. Software applications developers

  • Responsible for design, development and modification of software systems
  • Analyze user needs and software requirements to achieve a time and cost-effective design
  • Supervise the work of programmers, technologists and technicians
Median annual salary: $92,660
Projected growth (2012-2022): 22 percent

8. Public relations specialists

  • Prepare or edit organizational publications for internal and external audiences
  • Consult with advertising agencies or staff to arrange promotional campaigns in all types of media for products, organizations or individuals
  • Confer with production to produce or coordinate implementation of advertisements or promotions
Median annual salary: $54,940
Projected growth (2012-2022): 12 percent

9. Marketing managers

  • Identify, develop or evaluate marketing strategies
  • Formulate, direct and coordinate marketing activities and policies to promote products and services
  • Consult with buying personnel to gain advice regarding the products expected to be in demand
Median annual salary: $123,220
Projected growth (2012-2022): 12 percent

10. Commercial and industrial designers

  • Work with various departments to establish and evaluate design concepts for manufactured products
  • Prepare sketches of ideas, detailed drawings, illustrations, artwork or blueprints
  • Direct and coordinate the fabrication of models or samples and the drafting of working drawings
Median annual salary: $62,370
Projected growth (2012-2022): 5 percent

Friday, 1 July 2016

Creating Bootable Vista / Windows 7 USB Flash Drive

Microsoft Provides a tool to do this for you – Windows 7 USB/DVD Download Tool. See the Microsoft Store Help on the ISO-Tool (http://store.microsoft.com/Help/ISO-Tool).
It surprised me to find that there are very few dead-simple guides to creating a bootable USB thumb/pen/flash drive for a Vista and/or Windows 7 installation.  I cobbled together the following from VistaPCGuy and another source I don’t remember right now.
This will walk through the steps to create a bootable USB flash drive for the purpose of installing a Vista or Windows 7 OS.  These instructions assume that you have a computer with Windows Vista installed on it.

Required:
  • USB Flash Drive (4GB+)
  • Microsoft OS Disk (Vista / Windows 7)
  • A computer running Vista / Windows 7
Step 1: Format the Drive
The steps here are to use the command line to format the disk properly using the diskpart utility. [Be warned: this will erase everything on your drive. Be careful.]
  1. Plug in your USB Flash Drive
  2. Open a command prompt as administrator (Right click on Start > All Programs > Accessories > Command Prompt and select “Run as administrator”
  3. Find the drive number of your USB Drive by typing the following into the Command Prompt window:
    diskpart
    list disk
    The number of your USB drive will listed. You’ll need this for the next step.  I’ll assume that the USB flash drive is disk 1.
  4. Format the drive by typing the next instructions into the same window. Replace the number “1” with the number of your disk below.
    select disk 1
    clean
    create partition primary
    select partition 1
    active
    format fs=NTFS
    assign
    exit
    When that is done you’ll have a formatted USB flash drive ready to be made bootable.
Step 2: Make the Drive Bootable
Next we’ll use the bootsect utility that comes on the Vista or Windows 7 disk to make the flash drive bootable.  In the same command window that you were using in Step 1:
  1. Insert your Windows Vista / 7 DVD into your drive.
  2. Change directory to the DVD’s boot directory where bootsect lives:
    d:
    cd d:\boot
  3. Use bootsect to set the USB as a bootable NTFS drive prepared for a Vista/7 image. I’m assuming that your USB flash drive has been labeled disk G:\ by the computer:
    bootsect /nt60 g:
  4. You can now close the command prompt window, we’re done here.
Step 3: Copy the installation DVD to the USB drive
The easiest way is to use Windows explorer to copy all of the files on your DVD on to the formatted flash drive.  After you’ve copied all of the files the disk you are ready to go.
Step 4: Set your BIOS to boot from USB
This is where you’re on your own since every computer is different. Most BIOS’s allow you to hit a key at boot and select a boot option.

Tuesday, 28 June 2016

DATA STRUCTURES NOTES

This algorithm comes under the greedy method, which means that the objects are chosen to join a growing collection by iteratively picking an object that minimizes some cost function.

Now, taking account of the above mentioned greedy method, the Prim-Jarnik's algorithm is similar to the Dijkstra's shortest-path algorithm to grow the Minimum Spanning Tree (MST) from a single cluster starting with a randomly chosen single root vertex.

The Prim-Jarnik's algorithm can be broken down as follows:
Step 1: Define the starting "cloud" of vertices [C] by selecting some random vertex [v] initially
Step 2: Iteratively choose a min-weight edge [e=(v,u)], thereby connecting a vertex [v] in the cloud [C] to a vertex [u] outside of [C]. After choosing [e] the vertex [u] is brought into the cloud [C] continuously until a spanning tree emerges.


Pseudo-code of the Prim-Jarnik's algorithm
// Prim-Jarnik(G) [Time complexity = O(m * log * n)]
// Input: A weighted connected graph [G] with n number of vertices & m number of edges
// Output: A minimum spanning tree [T] for [G]

// Pick a root vertex [v] of [G]
D[v] <- 0

// All vertices connected to the root vertex, hence it necessary to define the cost function.
// The cost function "D[u] = +infinity" when vertex [u] doesn't connect to vertex [v].
for each vertex u != v do
D[u] <- +infinity

// Initialise the MST
T <- null 

// Initialise a priority queue Q with an entry ((u,null),D[u]) for each vertex [u],
// where (u,null) is the element & D[u] in the key
while Q is not empty do
(u,e) <- Q.removeMin()
Add vertex u and edge e to T

// Perform the relaxation procedure on the edge of the vertex [z] adjacent to [u]
For each vertex z adjacent to u such that z is in Q do
if W((u,z)) <>
D[z] <- W((u,z))
Change to (z,(u,z)) the element of vertex z in Q
Change to D[z] the key of vertex z in Q
return the tree T










Kruskal's algorithm for extracting Minimum Spanning Tree (MST)

This algorithm comes under the greedy method, which means that the objects are chosen to join a growing collection by iteratively picking an object that minimizes some cost function.

Now, taking account of the above mentioned greedy method, the Kruskal's algorithm with a graph considers the edges in order of their weights to grow the Minimum Spanning Tree (MST) in clusters.

The Kruskal's algorithm can be broken down as follows:
Step 1: In a given undirected graph [G] consider each vertex is in its own cluster all by itself i.e. if a [G] has four vertices then you have four cluster initially
Step 2: Look for each edges in turn, ordered by increasing weight i.e. arrange all the edges in ascending order
Step 3: Start with the smallest weighing edge. If this edge connects two different clusters then it is considered as the min-weight "bridge" edge [e] and added to the set of edges of the MST. In this initial stages, due to addition of [e] to the MST (i.e. the growth of the MST), the two clusters then are merged into a single cluster. However, if a given [e] connects to two vertices that are already in the identified cluster then this [e] is discarded.
Step 4: Now iteratively the algorithm adds enough [e] to a set of edges of spanning tree, it terminates and outputs this tree as the MST.


Pseudo-code of the Kruskal's algorithm
// Kruskal(G) [Time complexity = O(m * log * n)]
// Input: A simple connected weight graph [G] with [n] vertices and [m] edges
// Output: A minimum spanning tree [T] for [G]
for each vertex [v] in [G] do
Define an elementary cluster C(v) <- {v}

// Initialise a priority queue Q to contain all edges in [G], using the weights as keys
T <- null 
// The above [T] will ultimately contain the edges of the MST

while [T] has fewer then n-1 edges do
(u,v) <- Q.removeMin()
// Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
if C(v) != C(u) the
Add edges (v,u) to T
Merge C(v) & C(u)
// The above union of C(v) & C(u) yields a single cluster
return tree TExample below shows the Kruskal's algorithm that extracts the MST from a spanning tree. This spanning tree depicts a subset of Finnish intercity roadways route:

--------------------------------------------
Stage 1.
--------------------------------------------
Main cluster (C) contains the following vertices: null
Elementary Cluster (C1) contains the following vertices: null

Priority Queue (Q)
------------------
----
110
----
137
---
141
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {null}
Set of discarded edges d = {null}

--------------------------------------------
Stage 2.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere

Priority Queue (Q)
------------------
----
137
---
141
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110}
Set of discarded edges d = {null}

--------------------------------------------
Stage 3.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere
Elementary Cluster (C2) contains the following vertices: Helsinki+Kouvola

Priority Queue (Q)
------------------
---
141
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,}
Set of discarded edges d = {null}

--------------------------------------------
Stage 4.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku
Elementary Cluster (C2) contains the following vertices: Helsinki+Kouvola

Priority Queue (Q)
------------------
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141}
Set of discarded edges d = {null}

--------------------------------------------
Stage 5.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola

Priority Queue (Q)
------------------
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,}
Set of discarded edges d = {null}

--------------------------------------------
Stage 6.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola

Priority Queue (Q)
------------------
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,}
Set of discarded edges d = {177,}

--------------------------------------------
Stage 7.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio

Priority Queue (Q)
------------------
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294}
Set of discarded edges d = {177,}

--------------------------------------------
Stage 8.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio

Priority Queue (Q)
------------------
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294,}
Set of discarded edges d = {177,381}

--------------------------------------------
Stage 9.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio

Priority Queue (Q)
------------------
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294}
Set of discarded edges d = {177,381,409}

--------------------------------------------
Stage 10.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio+Oulu

Priority Queue (Q)
------------------
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294,534,}
Set of discarded edges d = {177,381,409}

--------------------------------------------
Stage 11.
--------------------------------------------
Main cluster (C) contains the following vertices = C1
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio+Oulu+Ivalo

Priority Queue (Q)
------------------
null
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294,534,549}
Set of discarded edges d = {177,381,409}









Spanning Tree & Minimum Spanning Tree (MST)

Spanning Tree - A tree that contains every vertex of a connected graph G is referred to as a spanning tree. The below figure depicts the Finnish intercity roadways route as a sapnning tree.



Minimum Spanning Tree (MST) - the problem of computing a spanning tree with the smallest total weight is known as the Minimum Spanning Tree problem. The below figure depicts the MST that houses a collection of smallest weighted routes between the Finnish cities. Routes not taken into the MST are: 177,381,409.


Friday, March 27, 2009


Application of a Binary Tree

The binary tree are applicable in the below mentioned fields:
- Used in the compilers of high-level programming languages for intermediate representation
- Used as a searching technique
- Used in databases for storing data
- To solve arithmetic expressions

Exercise-Binary Tree Construction

Given data items: 17, 6, 3, 9 ,12, 15, 1, 18, 22
The resulting binary tree is:


What is a Binary Tree?

A binary tree embodies a finite set of data items that is either empty or partitioned into three disjoint subsets. The first part contains a single data item referred to as the root of the binary tree, other two data items are left and right subtrees. These data items is referred to as nodes of the binary tree.

From this figure we can portray the following:
A - Root node of the binary tree
A - Parent node of the nodes B & C
B & C - Children nodes of A and these nodes are in a level one more than the root node A
C - Right child node of A
B - Left child node of A
D & E - These node are without a child, so they are referred to as leafs or external nodes
B & C - These nodes have a child each, so they are referred to as internal nodes

Depth of this binary tree - The longest path from the root node A to any leaf node, for example D node. Therefore, the depth of this binary tree is two.
Indegree of a node - The number of edges merging into a node. For example, indegree of the node B is one i.e. one edge merges.
Outdegree of a node - The number of edges coming out from a node. For example, outdegree of the node A is two i.e. two edges comes out of this root node.

Concerning the binary trees, do refer to the following blog entries:
- Exercise-Binary Tree Construction
- Application of a Binary Tree

What is a Complete Binary Tree?

A strictly binary tree of depth 'd' in which all the leaves are at level 'd' i.e. there is non empty left or right subtrees and leaves are populated at the same level.
In a complete binary tree all the internal nodes have equal degree, which means that one node at the root level, two nodes at level 2, four nodes at level 3, eight nodes at level 4, etc, which the below figure represents:
This algorithm comes under the greedy method, which means that the objects are chosen to join a growing collection by iteratively picking an object that minimizes some cost function.

Now, taking account of the above mentioned greedy method, the Prim-Jarnik's algorithm is similar to the Dijkstra's shortest-path algorithm to grow the Minimum Spanning Tree (MST) from a single cluster starting with a randomly chosen single root vertex.

The Prim-Jarnik's algorithm can be broken down as follows:
Step 1: Define the starting "cloud" of vertices [C] by selecting some random vertex [v] initially
Step 2: Iteratively choose a min-weight edge [e=(v,u)], thereby connecting a vertex [v] in the cloud [C] to a vertex [u] outside of [C]. After choosing [e] the vertex [u] is brought into the cloud [C] continuously until a spanning tree emerges.


Pseudo-code of the Prim-Jarnik's algorithm
// Prim-Jarnik(G) [Time complexity = O(m * log * n)]
// Input: A weighted connected graph [G] with n number of vertices & m number of edges
// Output: A minimum spanning tree [T] for [G]

// Pick a root vertex [v] of [G]
D[v] <- 0

// All vertices connected to the root vertex, hence it necessary to define the cost function.
// The cost function "D[u] = +infinity" when vertex [u] doesn't connect to vertex [v].
for each vertex u != v do
D[u] <- +infinity

// Initialise the MST
T <- null 

// Initialise a priority queue Q with an entry ((u,null),D[u]) for each vertex [u],
// where (u,null) is the element & D[u] in the key
while Q is not empty do
(u,e) <- Q.removeMin()
Add vertex u and edge e to T

// Perform the relaxation procedure on the edge of the vertex [z] adjacent to [u]
For each vertex z adjacent to u such that z is in Q do
if W((u,z)) <>
D[z] <- W((u,z))
Change to (z,(u,z)) the element of vertex z in Q
Change to D[z] the key of vertex z in Q
return the tree T








Kruskal's algorithm for extracting Minimum Spanning Tree (MST)

This algorithm comes under the greedy method, which means that the objects are chosen to join a growing collection by iteratively picking an object that minimizes some cost function.

Now, taking account of the above mentioned greedy method, the Kruskal's algorithm with a graph considers the edges in order of their weights to grow the Minimum Spanning Tree (MST) in clusters.

The Kruskal's algorithm can be broken down as follows:
Step 1: In a given undirected graph [G] consider each vertex is in its own cluster all by itself i.e. if a [G] has four vertices then you have four cluster initially
Step 2: Look for each edges in turn, ordered by increasing weight i.e. arrange all the edges in ascending order
Step 3: Start with the smallest weighing edge. If this edge connects two different clusters then it is considered as the min-weight "bridge" edge [e] and added to the set of edges of the MST. In this initial stages, due to addition of [e] to the MST (i.e. the growth of the MST), the two clusters then are merged into a single cluster. However, if a given [e] connects to two vertices that are already in the identified cluster then this [e] is discarded.
Step 4: Now iteratively the algorithm adds enough [e] to a set of edges of spanning tree, it terminates and outputs this tree as the MST.


Pseudo-code of the Kruskal's algorithm
// Kruskal(G) [Time complexity = O(m * log * n)]
// Input: A simple connected weight graph [G] with [n] vertices and [m] edges
// Output: A minimum spanning tree [T] for [G]
for each vertex [v] in [G] do
Define an elementary cluster C(v) <- {v}

// Initialise a priority queue Q to contain all edges in [G], using the weights as keys
T <- null 
// The above [T] will ultimately contain the edges of the MST

while [T] has fewer then n-1 edges do
(u,v) <- Q.removeMin()
// Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
if C(v) != C(u) the
Add edges (v,u) to T
Merge C(v) & C(u)
// The above union of C(v) & C(u) yields a single cluster
return tree T
Example below shows the Kruskal's algorithm that extracts the MST from a spanning tree. This spanning tree depicts a subset of Finnish intercity roadways route:

--------------------------------------------
Stage 1.
--------------------------------------------
Main cluster (C) contains the following vertices: null
Elementary Cluster (C1) contains the following vertices: null

Priority Queue (Q)
------------------
----
110
----
137
---
141
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {null}
Set of discarded edges d = {null}

--------------------------------------------
Stage 2.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere

Priority Queue (Q)
------------------
----
137
---
141
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110}
Set of discarded edges d = {null}

--------------------------------------------
Stage 3.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere
Elementary Cluster (C2) contains the following vertices: Helsinki+Kouvola

Priority Queue (Q)
------------------
---
141
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,}
Set of discarded edges d = {null}

--------------------------------------------
Stage 4.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku
Elementary Cluster (C2) contains the following vertices: Helsinki+Kouvola

Priority Queue (Q)
------------------
---
164
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141}
Set of discarded edges d = {null}

--------------------------------------------
Stage 5.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola

Priority Queue (Q)
------------------
---
177
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,}
Set of discarded edges d = {null}

--------------------------------------------
Stage 6.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola

Priority Queue (Q)
------------------
---
294
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,}
Set of discarded edges d = {177,}

--------------------------------------------
Stage 7.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio

Priority Queue (Q)
------------------
---
381
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294}
Set of discarded edges d = {177,}

--------------------------------------------
Stage 8.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio

Priority Queue (Q)
------------------
---
409
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294,}
Set of discarded edges d = {177,381}

--------------------------------------------
Stage 9.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio

Priority Queue (Q)
------------------
---
534
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294}
Set of discarded edges d = {177,381,409}

--------------------------------------------
Stage 10.
--------------------------------------------
Main cluster (C) contains the following vertices:null
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio+Oulu

Priority Queue (Q)
------------------
---
549
---
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294,534,}
Set of discarded edges d = {177,381,409}

--------------------------------------------
Stage 11.
--------------------------------------------
Main cluster (C) contains the following vertices = C1
Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio+Oulu+Ivalo

Priority Queue (Q)
------------------
null
------------------

Set of min-weight "bridge" edges e = {110,137,141,164,294,534,549}
Set of discarded edges d = {177,381,409}







Spanning Tree & Minimum Spanning Tree (MST)

Spanning Tree - A tree that contains every vertex of a connected graph G is referred to as a spanning tree. The below figure depicts the Finnish intercity roadways route as a sapnning tree.



Minimum Spanning Tree (MST) - the problem of computing a spanning tree with the smallest total weight is known as the Minimum Spanning Tree problem. The below figure depicts the MST that houses a collection of smallest weighted routes between the Finnish cities. Routes not taken into the MST are: 177,381,409.

Friday, March 27, 2009

Application of a Binary Tree

The binary tree are applicable in the below mentioned fields:
- Used in the compilers of high-level programming languages for intermediate representation
- Used as a searching technique
- Used in databases for storing data
- To solve arithmetic expressions

Exercise-Binary Tree Construction

Given data items: 17, 6, 3, 9 ,12, 15, 1, 18, 22
The resulting binary tree is:

What is a Binary Tree?

A binary tree embodies a finite set of data items that is either empty or partitioned into three disjoint subsets. The first part contains a single data item referred to as the root of the binary tree, other two data items are left and right subtrees. These data items is referred to as nodes of the binary tree.

From this figure we can portray the following:
A - Root node of the binary tree
A - Parent node of the nodes B & C
B & C - Children nodes of A and these nodes are in a level one more than the root node A
C - Right child node of A
B - Left child node of A
D & E - These node are without a child, so they are referred to as leafs or external nodes
B & C - These nodes have a child each, so they are referred to as internal nodes

Depth of this binary tree - The longest path from the root node A to any leaf node, for example D node. Therefore, the depth of this binary tree is two.
Indegree of a node - The number of edges merging into a node. For example, indegree of the node B is one i.e. one edge merges.
Outdegree of a node - The number of edges coming out from a node. For example, outdegree of the node A is two i.e. two edges comes out of this root node.

Concerning the binary trees, do refer to the following blog entries:
- Exercise-Binary Tree Construction
- Application of a Binary Tree

What is a Complete Binary Tree?

A strictly binary tree of depth 'd' in which all the leaves are at level 'd' i.e. there is non empty left or right subtrees and leaves are populated at the same level.
In a complete binary tree all the internal nodes have equal degree, which means that one node at the root level, two nodes at level 2, four nodes at level 3, eight nodes at level 4, etc, which the below figure represents:

Excel Formula's (Regular & Job-Oriented)

 Excel Formula's  1) SUM Task: Sum of numbers Formula: =SUM(A1:A10) Example: Sum of all numbers in A1–A10 2) AVERAGE Task: Average Formu...